package OptimalAlgorithm.String;

import java.util.Stack;

//https://leetcode.cn/problems/longest-palindromic-substring/description/
public class LongestPalindrome {
    //方法一：暴力枚举法
/*    public String longestPalindrome(String s) {
        if(isPalindrome(s,0,s.length() - 1)){
            return s;
        }
        int len = 0;
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if(isPalindrome(s,i,j)){
                    int Len = len;
                    len = Math.max(len,j - i + 1);
                    if(Len != len){
                        index = i;
                    }
                }
            }
        }
        return s.substring(index,len + index);
    }
    private Boolean isPalindrome(String s,int left,int right){
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }*/
    //方法二：中心扩展法（利用回文串特性）
    public String longestPalindrome(String s) {
        int len = 0;
        int index = 0;
        for (int i = 0; i < s.length(); i++) {//i表示固定的中心点
            //从中心点开始，向两边扩展
            int left = i;
            int right = i;
            int oddLen = 0;
            int oddIndex = 0;
            int evenIndex = 0;
            int evenLen = 0;
            while (right < s.length() && left >= 0 && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            oddIndex = left + 1;
            oddLen = right - left - 1;
            if(oddLen > len){
                len = oddLen;
                index = oddIndex;
            }
            left = i;right = i + 1;
            while (right < s.length() && left >= 0 && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            evenIndex = left + 1;
            evenLen = right - left - 1;
            if(evenLen > len){
                len = evenLen;
                index = evenIndex;
            }
        }
        return s.substring(index,len + index);
    }
}
